class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        vector<int> dp(n + 1, 0);

        int ans = 0;
        for (int i = 1; i < n; i++)
        {
            if (s[i] == '(')
                dp[i] = 0;
            else
            {
                int p = i - 1 - dp[i - 1];
                int tmp = p - 1 >= 0 ? dp[p - 1] : 0;
                if (p < 0)
                    continue;
                if (s[p] == '(')
                    dp[i] = dp[i - 1] + 2 + tmp;

            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};